package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/*
递归遍历二叉树
前序 中序 后续
 */
public class Of20210114QueryTree {
    public static void main(String[] args) {
        System.out.println(afterTraversal(new TreeNode(1, new TreeNode(2, new TreeNode(4)
                , new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)))));
    }

    /*
    前序遍历
     */
    private static List<Integer> beforeTraversal(TreeNode cur) {
        ArrayList<Integer> result = new ArrayList<>();
        if (cur == null) return result;
        result.add(cur.val);    // 中
        result.addAll(beforeTraversal(cur.left));  // 左
        result.addAll(beforeTraversal(cur.right)); // 右
        return result;
    }
    private static List<Integer> midTraversal(TreeNode cur) {
        ArrayList<Integer> result = new ArrayList<>();
        if (cur == null) return result;
        result.addAll(midTraversal(cur.left));  // 左
        result.add(cur.val);    // 中
        result.addAll(midTraversal(cur.right)); // 右
        return result;
    }
    private static List<Integer> afterTraversal(TreeNode cur) {
        ArrayList<Integer> result = new ArrayList<>();
        if (cur == null) return result;
        result.addAll(afterTraversal(cur.left));  // 左
        result.addAll(afterTraversal(cur.right)); // 右
        result.add(cur.val);    // 中
        return result;
    }
}
